1. Field of the Invention
The invention relates to the field of communication. More specifically, the invention relates to communication networks.
2. Background of the Invention
The border gateway protocol (BGP) is defined by RFC 1771. BGP requires that network elements within the same autonomous system to have a full mesh communications. Having full mesh communications doesn't require each network element of the autonomous system to be physically linked with all other network elements of the autonomous system, but it does require each network element to have a BGP session with all other network elements within the same autonomous system. This full mesh communication requirement encounters a scalability problem. Confederations and route reflection, as respectively defined by RFC 1965 and RFC 1966, are proposed alternative solutions to the scalability problem.
FIG. 1 (Prior Art) is a diagram illustrating confederations. In FIG. 1, an autonomous system 103A includes a confederation 105A and a confederation 105B. Each network element of a confederation must satisfy the full mesh requirement. The confederation 105A includes network elements 101A-101C. The confederation 105B includes network elements 101D-101F. The network elements 101A and 101D respectively act as border routers for the confederations 105A and 105B. The network element 101B is an autonomous system border router (ASBR) that communicates with an autonomous system 103B. The network element 101D also acts as an ASBR that communicates with an autonomous system 103C.
FIG. 2 (Prior Art) is a diagram illustrating route reflection. An autonomous system 203A includes a cluster 205A and a cluster 205B. The cluster 205A includes a route reflector 201A and network elements 207A and 207C. The cluster 205B includes a route reflector 201B and network elements 207E and 207F. The route reflector 201A has BGP sessions with the network elements 207A and 207C. Likewise, the route reflector 201B has BGP sessions with network elements 207E and 207F. The network element 207A is an ASBR that communicates with an autonomous system 203B. Similarly, the network element 201B also acts as an ASBR that communicates with an autonomous system 203C.
FIG. 3 (Prior Art) is a flowchart for processing a BGP message that indicates a route. A route reflector and a confederation border router handle route advertisements and process routing messages as illustrated in the flowchart a FIG. 3. At block 301, a routing protocol message indicating a route to a destination is received. If the routing protocol message is a withdrawal message, then control flows to block 303. If the routing protocol message is an advertisement/update message, then control flows to block 305.
At block 305, the route is inserted into the routing table. From block 305, control flows to block 307.
At block 303, the route is removed from the routing table. From block 303, control flows to block 307.
At block 307, a best route to the destination is calculated. At block 309, if the best route has changed, then an update message indicating the new best route is sent to all peers.
FIG. 4 (Prior Art) is a diagram illustrating data structures for tracking routes. In FIG. 4, a network element 409 has BGP sessions with an external peer (i.e., a route reflector of a different cluster or a border router of a different confederation) 413 and internal peers 411A and 411B (i.e., a peer within the same cluster or a peer within the same confederation). The network element 409 includes a BGP routing table entry 401. The BGP routing table entry indicates a destination, a route pointer, and a best route pointer. The route pointer points to the head of a list of routes 403. The list of routes 403 in FIG. 4 includes route data structures 402A-402C. Each of the route data structures 402A-402C indicates a route, including AS_PATH, MED, NEXT_HOP, etc. In FIG. 4, the best route pointer of the BGP routing table entry 401 references the route data structure 402B. Therefore, the network element 409 transmits to the external peer 413 and the internal peers 411A and 411B a BGP routing message that indicates the route of the route data structure 402B.
Unfortunately, in certain situations, a communication of a best route by a route reflector or a confederation border router causes route oscillation, which typically occurs within the same autonomous system.